Bus Routes

Try to solve the Bus Routes problem.

We'll cover the following

Statement#

You are given an array, routes, representing bus routes where routes[i] is a bus route that the ithi^{th} bus repeats forever. Every route contains one or more stations. You have also been given the source station, src, and a destination station, dest. Return the minimum number of buses someone must take to travel from src to dest, or return -1 if there is no route.

Constraints:

  • 1≤1 \le routes.length ≤500\le 500
  • 1≤1 \le routes[i].length ≤103\le 10^3
  • 0≤0 \le routes[i][j] <105< 10^5
  • 0≤0 \le src, dest <105< 10^5

Examples#

Created with Fabric.js 3.6.6 Sample example 1 Output = 2 Bus Routes = [[2, 5, 7], [4, 6, 7]] ----------------------------------- src = 2dest = 6

1 of 3

Created with Fabric.js 3.6.6 Sample example 2 Bus Routes = [[1, 12], [10, 5, 9], [4, 19], [10, 12, 13]] Output = 3 ----------------------------------- src = 1dest = 9

2 of 3

Created with Fabric.js 3.6.6 Sample example 3 Bus Routes = [[1, 12], [4, 5, 9], [9, 19], [10, 12, 13]] Output = -1 There is no bus route fromsrc=9 to dest=12. ----------------------------------- src = 9dest = 12

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

3

What is the output if the following input is given?

Bus routes = [[4, 7, 9], [6, 8, 9]]

src = 4

dest = 8

Your Answer
A)

1

Correct Answer
B)

2

Explanation

Start with a bus at station 4, and take it to station 9. Finally, take another bus from station 9 to station 8.

C)

3

D)

-1

Question 3 of 33 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create an adjacency list that maps each station to the buses that travel through that station.

Initialize a queue with a source station and the bus count.

Iterate the queue either till it is empty or the destination station has arrived.

Visit connecting stations of the dequeued station, and enqueue connecting stations.

In every iteration, increase the bus count if a new bus is passing through the same station.

Return the bus count.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Powered by AI
Input #1
Input #2
Input #3
Bus Routes

Solution: Graph Valid Tree

Solution: Bus Routes